#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//设d[k][i]为i天进行了k比交易手上还存在一支股票所占的最大利润
//设p[k][i]为第i天进行了k比交易手上没有一只股票所占的最大利润
// int d[1005][1005];
// int p[1005][1005];

// class Solution {
// public:
//     int maxProfit(int k, vector<int>& prices) {
//         for(int i = 0; i<prices.size();++i){
//             d[0][i] = -prices[0];
//         }   
//         for(int i=1;i<=k;++i){
//             for(int j = i;j<prices.size();++j){
//                 p[i][j] = max(d[i-1][j-1]+prices[j],p[i][j-1]);
//                 d[i][j] = max(p[i][j-1]-prices[j],d[i][j-1]);
//             }
//         }
//         return max(p[k][prices.size()-1],d[k][prices.size()-1]);
//     }
// };

// int main(){
//     Solution S;
//     vector<int> prices = {2,4,1};
//     cout<<S.maxProfit(2,prices)<<endl;
// }

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        // k = min(k, n / 2);
        vector<vector<int>> buy(n, vector<int>(k + 1));
        vector<vector<int>> sell(n, vector<int>(k + 1));

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = INT_MIN / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }

        return *max_element(sell[n - 1].begin(), sell[n - 1].end());
    }
};


int main(){
    Solution S;
    vector<int> prices = {2,4,1};
    cout<<S.maxProfit(2,prices)<<endl;
}